package backtrack

import "fmt"

var result [8]int

// cal8queens 生成8皇后数组
func cal8queens(row int) {
	if row == 8 {
		print8queens()
		return
	}

	for column := 0; column < 8; column++ {

		if isOk(row, column) {
			result[row] = column
			cal8queens(row + 1)
		}
	}

}

// 当前行的数据放在这一列是否OK
func isOk(row, column int) bool {
	// 左上对角线和右上对角线
	leftUp, rightUp := column-1, column+1
	// 回溯之前的行上的皇后是否和当前列在系统
	for r := row - 1; r >= 0; r-- {
		// 是否是同一列
		if result[r] == column {
			return false
		}
		if leftUp >= 0 && leftUp == result[r] {
			return false
		}

		if rightUp < 8 && rightUp == result[r] {
			return false
		}

		leftUp--
		rightUp++
	}
	return true
}

func print8queens() {

	for column, index := range result {
		fmt.Printf("the %d row queen in %d\n", index, column)
	}

}
